/** \file    indexed_vector.h
  * \brief   Specialized data structure: vector of elements having unique index.
  * \date    2002
  * \author  Fedor Chelnokov
  * \version $Header: /home/cscom1r4/cvsroot/cs/include/xtd/indexed_vector.h,v 1.1 2005/04/04 04:10:16 cscom1r4 Exp $
  */

#ifndef _indexed_vector_h_
#define _indexed_vector_h_

#include <vector>
#include <map>
#include <cassert>

namespace xtd {

//E - type of vector's element, should implement:
//typedef index_type - defines type of index' element
//funtion index() returning index associated with the called object.

template <class E>
class indexed_vector
{
public:
	typedef E								value_type;
	typedef typename E::index_type			index_type;
	typedef std::vector<E>					elem_vector;
	typedef typename elem_vector::size_type	size_type;
	typedef std::map<index_type, size_type>	index_seqnum_map;
	typedef typename elem_vector::iterator	iterator;
	typedef typename elem_vector::const_iterator	const_iterator;

public:
	size_type size() const 
		{ return _elems.size(); }
	void clear()
		{ _index_seqnum_map.clear();
		  _elems.clear(); }

	iterator begin() 
		{ return _elems.begin(); }
	const_iterator begin() const 
		{ return _elems.begin(); }
	iterator end() 
		{ return _elems.end(); }
	const_iterator end() const 
		{ return _elems.end(); }

	size_type seqnum(index_type index) const
		{ index_seqnum_map::const_iterator i = _index_seqnum_map.find(index);
		  assert(i != _index_seqnum_map.end());
		  return i->second; }
	//return -1 if no element found
	int find_seqnum(index_type index) const
		{ index_seqnum_map::const_iterator i = _index_seqnum_map.find(index);
		  return i==_index_seqnum_map.end() ? -1 : (int)i->second; }

	//access by sequential number, element should exist
	E &operator [] (size_type seqnum)
		{ return _elems[seqnum]; }
	const E &operator [] (size_type seqnum) const
		{ return _elems[seqnum]; }

	//access by index, element should exist
	E &operator () (index_type index)
		{ return _elems[seqnum(index)]; }
	const E &operator () (index_type index) const
		{ return _elems[seqnum(index)]; }

	//result will be 0 if no element found
	E *find_by_index(index_type index)
		{ int i = find_seqnum(index);
		  return i == -1 ? 0 : &_elems[i]; }
	const E *find_by_index(index_type index) const
		{ int i = find_seqnum(index);
		  return i == -1 ? 0 : &_elems[i]; }

	//returns seq. number of the existing element with the same e.index(), or inserts e and returns one of it
	size_type insert(const E & e)
		{ std::pair<index_seqnum_map::iterator, bool> p =
			_index_seqnum_map.insert(index_seqnum_map::value_type(e.index(), _elems.size()));
		  if (p.second)
			_elems.push_back(e);
		  return p.first->second; }

	void swap(indexed_vector &x)
		{ _elems.swap(x._elems);
		  _index_seqnum_map.swap(x._index_seqnum_map); }

	//!non-standard behaviour for compatibility with MaskTracer
	///adds new element without appropriate index, returns seq. number of added element
	size_type append(const E & e)
		{ _elems.push_back(e);
		  return _elems.size()-1; }
	///resizes the container in smaller side (dropping elements added by append())
	void reduce(size_type new_size)
		{ assert(new_size <= _elems.size() && new_size >= _index_seqnum_map.size());
		  _elems.resize(new_size); }

private:
	index_seqnum_map	_index_seqnum_map;
	elem_vector			_elems;
};

} //namespace xtd 

#endif //_indexed_vector_h_
